package q501_findMode;

import CommonClass.Common.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class Solution_2 {
    /**
     * 如何减少时间复杂度和空间复杂度
     * 例如只遍历一次树就得到solution1的resList
     * （我们也可以中序遍历两次二叉树 第一次找出最大频率，第二次把等于这个频率的加入数组）
     * 如果要遍历一次找出全部众数
     * 则需要不断更新我们的结果集
     * 也就是如下所示
     *
     * @param root
     * @return
     */
    int maxCount = Integer.MIN_VALUE; // 最大频率
    int count = 0; // 统计频率
    TreeNode prev = null;// 上一节点
    List<Integer> resList = new ArrayList<>();// 结果集

    public int[] findMode(TreeNode root) {
        searchBST(root);
        int size = resList.size();
        int[] ans = new int[size];
        for(int i = 0; i < size; i++){
            ans[i] = resList.get(i);
        }
        return ans;
    }

    private void searchBST(TreeNode root) {
        if (root == null) {
            return;
        }

        // 中序遍历
        // 左
        searchBST(root.left);

        // 中
        // 注意节点的处理逻辑
        // 1 如果pre还是null 意味着当前dfs刚开始 此时先令count = 1
        // 2 或者不等也就意味着到了新的值 则令count初始化为1
        if(prev != null && root.val == prev.val){
            // 否则令count++
            count++;
        }else{
            count = 1;
        }



        // 每次有一个新节点被比较后，先比较count和记录的maxCount
        // 1 如果相等 则先加入该元素
        if (count == maxCount) {
            resList.add(root.val);
        }
        // 2 如果大于max 则先clear记录的List 然后重置maxCount 并加入新元素
        if (count > maxCount) {
            resList.clear();
            maxCount = count;
            resList.add(root.val);
        }

        prev = root;
        // 右
        searchBST(root.right);

    }
}
